前言
会在题目名称后给每道题目一个标记，标 ! 的是我认为非常好的 CNOI-Style 的题，标 * 的是构造题、结论题等比较 Ad-hoc 的题，标 + 的是思维含量比较高题。根据牛牛程度会增减数量。
CF1610I Mashtali vs AtCoder [**]
tags: 博弈论\verb|tags: 博弈论|tags: 博弈论
Green-Hackenbush：给定一张无向图，有一个根，两个人轮流操作，每次删掉一条边，然后删掉与根不连通的连通块，无法操作者输。
当图是树时即 AGC017D。结论为：
SG(u)=xorv∈son(u)(SG(v)+1)SG(u) = \mathop{\mathrm{xor}}\limits_{v \in \mathrm{son}(u)} (SG(v) + 1)
SG(u)=v∈son(u)xor(SG(v)+1)
回到原问题：当有多个根时，可以把这些根缩成一个点。
Fusion Principle：在 Green-Hackenbush 中，可以把一个偶环缩成一个点，把一个奇环缩成一个点下面再挂一个点，原本环外连向环上的边都连...
基本概念
对于求和式 ∑anxn\sum a_n x^n∑anxn，如果是有限项相加，则称为多项式。记错 F(x)=∑i=0naixiF(x) = \sum_{i = 0}^n a_i x^iF(x)=∑i=0naixi，其中 aia_iai 称为该多项式的 iii 次项系数，记作 [xi]F(x)[x^i]F(x)[xi]F(x)，有时也用 F[i]F[i]F[i] 表示。
定义两个多项式的 ⊕\oplus⊕ 运算卷积为：
[xn](F×G)(x)=∑i⊕j=n[xi]F(x)[xj]G(x)[x^n](F \times G)(x) = \sum\limits_{i \oplus j = n} [x^i]F(x)[x^j]G(x)
[xn](F×G)(x)=i⊕j=n∑[xi]F(x)[xj]G(x)
以下提到卷积一般指加法卷积。
FFT
多项式的点值表达：只需要 n+1n + 1n+1 个点值就可以唯一确定一个最高 nnn 次多项式。
两个多项式卷积就对应点值相乘。也就是对于任意 xxx，(F×G)(x)=F(x)G(x)(F \times G)(x) = F(...
洛谷 P7922 [Kubic] Pyramid 题解
题目链接
给定一个初始长度为 nnn 的序列 ppp。
设当前 ppp 的长度为 LLL，有以下两种操作：
A 操作先构造长度为 L−1L-1L−1 的序列 p′p'p′ 满足 pi′=min{pi,pi+1},i∈[1,L)p_i'=\min\{p_i,p_{i+1}\},i\in [1,L)pi′=min{pi,pi+1},i∈[1,L)。然后用 p′p'p′ 代替 ppp。
B 操作先构造长度为 L−1L-1L−1 的序列 p′p'p′ 满足 pi′=max{pi,pi+1},i∈[1,L)p_i'=\max\{p_i,p_{i+1}\},i\in [1,L)pi′=max{pi,pi+1},i∈[1,L)。然后用 p′p'p′ 代替 ppp。
再给定一个长度为 mmm 的序列 aaa，表示一共进行 mmm 组操作，第 iii 组中先进行 aia_iai 次 A 操作，再进行 aia_iai 次 B 操作。保证 2∑ai=n...
符号与约定
在本文中：
字符串索引默认从 111 开始。
用 s[l,r]s_{[l, r]}s[l,r] 表示子串 slsl+1sl+2…srs_l s_{l + 1} s_{l + 2} \ldots s_rslsl+1sl+2…sr，特别地，当 [l,r]=∅[l, r] = \varnothing[l,r]=∅ 时表示空串。
用 pre(s,i)\mathrm{pre}(s, i)pre(s,i) 表示 s[1,i]s_{[1, i]}s[1,i]，suf(s,i)\mathrm{suf}(s, i)suf(s,i) 表示 s[i,∣s∣]s_{[i, |s|]}s[i,∣s∣]。
定义
对于一个字符串 sss，若正整数 i<∣s∣i<|s|i<∣s∣ 满足 pre(s,i)=suf(s,∣s∣−i+1)\mathrm{pre}(s, i) = \mathrm{suf}(s, |s| - i + 1)pre(s,i)=suf(s,∣s∣−i+1)，则称 pre(s,i)\mathrm{pre}(s, i)pre(s,i) 为 sss 的...
Legacy
TopCoder XorBoard
给定 H,W,R,C,SH, W, R, C, SH,W,R,C,S，给一个 H×WH \times WH×W 的网格，初始全为白色，每次可以选一列或选一行白变黑、黑变白，问行操作 RRR 次，列操作 LLL 次，最终黑色面积为 SSS 的方案数。两种操作不同当且仅当存在一行或一列被操作的次数不同。
枚举染了几行几列然后算方案数即可。
TopCoder ConversionMachine
给定两个字符集为 {a,b,c}\{\texttt{a},\texttt{b},\texttt{c}\}{a,b,c} 的字符串 s,ts, ts,t，每次操作可以对 sss 的某个位置的字符向后变一位，给出每个字符变成下一个字符的代价和最大代价问把 sss 变成 ttt 的方案数。
每个位置都是先还原后再进行若干组 a→b→c→a\texttt{a} \to \texttt{b} \to \texttt{c} \to \texttt{a}a→b→c→a 的轮换，所以可以确定总的操作次数上限，然后设 dpi,jdp _ {i, j}...
Day1T1 季风 wind
Link
Day1T2 魔法手杖 xor
考虑扔 Trie 上，然后在 Trie 上游走，表示当前 U∖SU \setminus SU∖S 中 ⊕x{} \oplus x⊕x 后最小的值。
然后考虑往某个儿子走，若要 mini∈U∖Sai⊕x\min _ {i \in U \setminus S} a _ i \oplus xmini∈U∖Sai⊕x 这一位是 111 则需要把另一个儿子扔到 SSS 里，但是当走 111 的时候不一定 mini∈U∖Sai⊕x\min _ {i \in U \setminus S} a _ i \oplus xmini∈U∖Sai⊕x 这一位是 111 答案就更优，那这种情况就需要两种都跑一遍。
以上是考场想法。
考虑二分答案，这样就可以直接贪做到 O(nk2)O(n k ^ 2)O(nk2)，用压缩 Trie 可以优化到 O(nk)O(nk)O(nk)，但是毛想想就知道很难写。
不妨直接考虑最终答案，若答案这一位需要是 111，则除了 mini∈U∖Sai⊕x\min _ {i \in U \se...
连夜赶的，等有时间再稍微润色一下（
Day -1
Lynkcat & zhh 逆天模拟赛，没想到省选最后一次模拟赛还吃了依托大的。
然而竟然打到了比较高的名次，果然我只会打答辩场啊……
但是不得不说确实涨信心了（
Day 0
上午不想写题了，鉴赏了几首 hitorie 的歌，然后写了个凸包板子就去吃午饭了。
下午一点上车去杭州，车上看了一下洛谷省选计划的模拟赛题，然后打算听会歌，结果耳机没连上直接外放了！！！当场社死。
到酒店之后借 Gold 的板子打了会 Phigros。
（这里应该有一张图）
好评如潮，说明我省选会打得非常好（确信。
然后出去吃了个晚饭，晚上又看了一下之前校内模拟赛的题，发现有些题一点印象都没了。
看完之后继续打摆，最后复习了一下矩阵相关就睡觉了。
Day 1
杭师大的显示屏终于不是傻逼的 4 : 3 了，感动中国！
先看完三个题然后开始做 T1，看数据范围就知道是 O(n)O(n)O(n) 的，然后就考虑对于答案 mod n{} \bmod nmodn 同余的部分放一起求。刚开始假了一会，然后仔细思考发现旋转 45∘45 ^ \circ45∘...
前言
会在题目名称后给每道题目一个标记，标 ! 的是我认为非常好的 CNOI-Style 的题，标 * 的是构造题、结论题等比较 Ad-hoc 的题，标 + 的是思维含量比较高题。根据牛牛程度会增减数量。
CF868G El Toll Caves [!!+]
tags: 数学, 数论, 概率论\verb|tags: 数学, 数论, 概率论|tags: 数学, 数论, 概率论
首先最优策略在任意时刻任意两个洞穴被查看的次数之差一定不会超过 222，因此可以得到最优策略是第 iii 论查看 ikikik 到 ik+k−1ik + k - 1ik+k−1 之间的洞穴（模 nnn 意义下）。
然后可以发现将洞穴每 gcd(n,k)\gcd(n, k)gcd(n,k) 个切一段，每段内部的洞穴没有本质区别，因此可以将 n,kn, kn,k 都除掉 gcd(n,k)\gcd(n, k)gcd(n,k)。
考虑设 fif _ ifi 表示宝藏在第 iii 个洞穴内时查看的期望次数，则有：
fi={fi−k+1k≤i<n12+12(fi−k+n+1)0≤i<kf _ i =...
跳过证明，只写做法。
概念
网络（network）是指一张特殊的有向图 G=(V,E)G = (V, E)G=(V,E)。
EEE 中每条边 (u,v)(u, v)(u,v)，有一个被称为流量（capacity）的权值，记作 c(u,v)c(u, v)c(u,v)。若 (u,v)∉E(u, v) \notin E(u,v)∈/E，则可以认为 c(u,v)=0c(u, v) = 0c(u,v)=0。
VVV 中有两个特殊点：源点（source）sss 和汇点（sink）ttt。
对于一张网络 G=(V,E)G = (V, E)G=(V,E)，流（flow）定义为一个从边集到整数集或实数集的函数 f:E→Zf: E \to \mathbb{Z}f:E→Z 或 f:E→Rf: E \to \mathbb{R}f:E→R，其满足如下性质：
容量限制：对于每条边 (u,v)(u, v)(u,v)，流经该边的流量不得超过该边的容量，即 ∀(u,v),0≤f(u,v)≤c(u,v)\forall (u, v), 0 \le f(u, v) \le c(u, v)∀(u,v),0≤f(u,v...
问题描述
给出一个幺半群 (S,⋅)(S, \cdot)(S,⋅) 和元素 u,r∈Su, r \in Su,r∈S，以及一条直线 y=ax+bcy = \frac{a x + b}{c}y=cax+b。
画出平面中所有坐标为正整数的横线和竖线，维护一个 fff，初值为单位元 eee。
从原点出发，先向 yyy 轴正方向走直到到达直线与 yyy 的交点，然后沿直线走一直走到与 x=nx = nx=n 的交点为止。
每当经过一条横线时，执行 f←fuf \gets fuf←fu，经过一条竖线时执行 f←frf \gets frf←fr。特别地，在 yyy 轴上行走时不考虑竖线，同时经过横线和竖线时先执行前者。
求最终的 fff。记为 euclid(a,b,c,n,u,r)\mathrm{euclid}(a, b, c, n, u, r)euclid(a,b,c,n,u,r)。
其中 a,b≥0,n,c>0a, b \ge 0, n, c > 0a,b≥0,n,c>0。
万能欧几里得算法
分情况考虑。
设 m=⌊an+bc⌋m = \lfloor\frac{a...